/**
 * \file packrat.c
 **/

#include "packrat.h"
#include "mem.h"
#include "tuple.h"
#include "map.h"
#include "log.h"

/**
 * \brief Get a single rule from the grammar.
 **/
static inline RGrammarEntry r_grammar_get(RGrammar* grammar,
                                              int index);

/**
 * \brief Apply a rule for the given nonterminal.
 **/
static RSemantic r_prat_apply(RParsing* parsing, RNonterminal nterm,
                                  int precedence);

RSemantic r_prat_apply(RParsing* parsing, RNonterminal nterm,
                           int precedence)
{
  /* Find the given nonterminal in the grammar. TODO: This is inefficient,
   * nonterminals should be numbered sequentially from 0, and grammar should
   * be a O(1) lookup vector. */
  int i;
  for (i = 0; i < parsing->grammar->size; i++){
    RGrammarEntry entry = r_grammar_get(parsing->grammar, i);
    if (nterm == entry.nonterminal)
      return entry.matcher(parsing, precedence);
  }
  return NULL;
}

bool r_prat_consume(RParsing* parsing, uint32_t type, void** extra)
{
  RToken token = r_tok_list_get(&parsing->tokens, parsing->idx);
  if (token.type == type){
    *extra = token.extra;
    parsing->idx++;
    return true;
  }
  return false;
}

void r_prat_grammar_add(RGrammar* grammar, RNonterminal nonterm,
                         RMatcher matcher)
{
  r_chunk_ensure_a((Chunk*) grammar, sizeof(RGrammar)
                     + (grammar->size + 1) * sizeof(RGrammarEntry));
  RGrammarEntry* entry = (RGrammarEntry*) (grammar + 1);
  entry[grammar->size].nonterminal = nonterm;
  entry[grammar->size].matcher = matcher;
  grammar->size++;
}

RGrammarEntry r_grammar_get(RGrammar* grammar, int index)
{
  RGrammarEntry* entry = (RGrammarEntry*) (grammar + 1);
  return entry[index];
}

#define R_DEFAULT_GRAMMAR 8
RGrammar* r_prat_grammar_new(void)
{
  RGrammar* grammar = (RGrammar*) r_chunk_new(sizeof(RGrammar)
                         + R_DEFAULT_GRAMMAR * sizeof(RGrammarEntry));
  grammar->size = 0;
  return grammar;
}

RSemantic r_prat_match(RParsing* parsing, RNonterminal nterm,
                           int precedence)
{
  /* Some documentation on parsing->map. Key-value pairs are the tuples:
   *
   * (int nonterminal, int index) -> (int status, pointer ast, int new_index)
   *
   * This function essentially applies the procedure that allows packrat
   * parsers to parse directly left-recursive rules. This algorithm was given
   * in "Packrat Parsers Can Support Left Recursion", A. Warth, J. R. Douglass,
   * T. Millstein. PEPM '08. */

  /* status value can be one of the following: */
  #define PRAT_APPLYING 0
  #define PRAT_DETECTED_LR 1
  #define PRAT_APPLIED 2

  /* Record the position on the start. */
  uint32_t idx = parsing->idx;

  /* Result of the map */
  RValue value;

  /* Create a key tuple on the stack to look up this match in the memo table.*/
  RValue key_tuple_stack[2] = {r_value_from_int32(nterm),
                                  r_value_from_int32(idx)};
  RValue key_stack = r_tuple_new(2, key_tuple_stack);
  if (r_map_get(parsing->map, key_stack, &value)){
    /* Found this match in memo table. */
    assert(r_value_is_tuple(value));
    assert(r_tuple_size(value) == 3);
    assert(r_value_is_int(value.val_tuple[0]));
    assert(r_value_is_pointer(value.val_tuple[1]));
    assert(r_value_is_int(value.val_tuple[2]));

    /* What is the status? */
    switch(value.val_tuple[0].val_int){
      case PRAT_APPLYING:
        value.val_tuple[0].val_int = PRAT_DETECTED_LR;
      case PRAT_DETECTED_LR:
        return NULL;
      case PRAT_APPLIED:
        parsing->idx = value.val_tuple[2].val_int;
        return value.val_tuple[1].val_p;
    }
  }

  /* Otherwise, keep going. Create a key tuple on the heap. */
  RValue* key_tuple_heap = (RValue*)
                                r_mem_malloc_a(2 * sizeof(RValue));
  key_tuple_heap[0] = r_value_from_int32(nterm);
  key_tuple_heap[1] = r_value_from_int32(idx);
  RValue key_heap = r_tuple_new(2, key_tuple_heap);

  /* memoize (nterm, idx) -> (APPLYING, NULL, idx). */
  RValue* value_tuple = (RValue*) r_mem_malloc(3 * sizeof(RValue));
  value_tuple[0] = r_value_from_int32(PRAT_APPLYING);
  value_tuple[1] = r_value_from_pointer(NULL);
  value_tuple[2] = r_value_from_int32(idx);
  value = r_tuple_new(3, value_tuple);
  r_map_set(parsing->map, key_heap, value);

  /* Apply the rule. */
  RSemantic result = r_prat_apply(parsing, nterm, precedence);
  if (result == NULL){
    /* Match failed, backtrack and memoize. */
    value.val_tuple[0].val_int = PRAT_APPLIED;
    value.val_tuple[1].val_p = NULL;
    value.val_tuple[2].val_int = idx;
    parsing->idx = idx;
    return NULL;
  } else if ((value.val_tuple[0].val_int == PRAT_APPLYING) or
             (value.val_tuple[0].val_int == PRAT_APPLIED)) {
    /* Match applied, no left recursion detected, memoize and return. */
    value.val_tuple[0].val_int = PRAT_APPLIED;
    value.val_tuple[1].val_p = result;
    value.val_tuple[2].val_int = parsing->idx;
    return result;
  } else if (value.val_tuple[0].val_int == PRAT_DETECTED_LR){
    /* Left recursion detected, now we "grow the seed". Begin by pretending
     * that a match succeeded at this place. */
    value.val_tuple[0].val_int = PRAT_APPLIED;
    value.val_tuple[1].val_p = result;
    value.val_tuple[2].val_int = parsing->idx;

    /* matched2 is the index reached in the latest attempt. matched1 is the
     * index reached in previous attempt. */
    uint32_t matched2 = parsing->idx;
    uint32_t matched1;
    do {
      matched1 = matched2;
      value.val_tuple[1].val_p = result;
      value.val_tuple[2].val_int = matched2;
      parsing->idx = idx; /* Backtrack to original call. */
      result = r_prat_apply(parsing, nterm, precedence);
      if (result == NULL)
        break;
      matched2 = parsing->idx;
    } while (matched2 > matched1);
    parsing->idx = matched1;
    return value.val_tuple[1].val_p;
  }
  assert_never();
  return NULL;
}

RParsing r_prat_new_parsing(RGrammar* grammar, RVector tokens)
{
  RParsing parsing;
  parsing.idx = 0;
  parsing.grammar = grammar;
  parsing.tokens = tokens;
  parsing.map = r_map_new_sized(500);
  return parsing;
}

RSemantic r_prat_parse(RParsing* parsing, RNonterminal start)
{
  parsing->idx = 0;
  /* This should be the larger than any other precedence */
  RSemantic result = r_prat_match(parsing, start, 0);
  return result;
}
